package stackExercise;

import java.util.Stack;

public class Test {
    //括号匹配
    /*
    * 1  若是左括号则入栈
    * 2  a若是右括号则进行匹配
    * 3  b栈为空
    * 4  栈不为空但字符串已经遍历完了
    **/
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        //开始匹配
        for(int  i = 0; i < s.length(); i++){
            char ch = s.charAt(i);
            //为左括号
            if(ch == '[' || ch == '{' || ch == '('){
                stack.push(ch);
            } else {
                //若栈为空
                if(stack.empty()){
                    return false;
                }
                //若为右括号
                char tmp = stack.peek();
                if((ch == ']' && tmp == '[') || (ch == '}' && tmp =='{') ||
                        (ch == ')' && tmp == '(')){
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        if(!stack.empty()){
            return false;
        }
        return true;
    }

    //逆波兰表达式求值
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for(String s : tokens){
            if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")){
                int m = stack.pop();
                int n = stack.pop();
                switch(s){
                    case "+":
                        stack.push(n + m);
                        break;
                    case "-":
                        stack.push(n - m);
                        break;
                    case "*":
                        stack.push(n * m);
                        break;
                    case "/":
                        stack.push(n / m);
                        break;
                }
            } else {
                stack.push(Integer.parseInt(s));
            }
        }
        return stack.pop();
    }

    //出站入栈次序匹配
    public static boolean isPopOrder(int [] pushA, int [] popA){
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for(int i = 0; i < pushA.length; i++){
            stack.push(pushA[i]);
            while(!stack.empty() && j < popA.length && popA[j] == stack.peek()){
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }
    public static void main(String[] args) {
        String s = "(())";
        isValid(s);
        int[] pushA = {1,2,3,4};
        int[] popB = {3,1,2,4};
        System.out.println(isPopOrder(pushA, popB));
    }
}
